home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / amiga / convrtrs / pbmplus / update5.lha / src / extra / ppmqvga.c < prev   
Encoding:
C/C++ Source or Header  |  1993-09-01  |  13.7 KB  |  518 lines
  1. /*
  2.  *  ppmqvga.c - quantize the colors in a pixmap down to a VGA
  3.  *    (256 colors, 6 bits per pixel)
  4.  *
  5.  *  original by Lyle Rains (lrains@netcom.com) as ppmq256 and ppmq256fs
  6.  *  combined, commented, and enhanced by Bill Davidsen (davidsen@crd.ge.com)
  7. */
  8.  
  9. #define DUMPCOLORS 0
  10. #define DUMPERRORS 0
  11.  
  12. #include <stdio.h>
  13. #include <math.h>
  14. #include <stdlib.h>
  15. #include "ppm.h"
  16. #ifdef SYSV
  17. #include <string.h>
  18. #define srandom srand
  19. #define random rand
  20. #else /*SYSV*/
  21. #include <strings.h>
  22. #define strchr index
  23. #define strrchr rindex
  24. #endif /*SYSV*/
  25.  
  26. #define min(a,b) ((a) < (b) ? (a) : (b))
  27. #define max(a,b) ((a) > (b) ? (a) : (b))
  28.  
  29. #define RED_BITS   5
  30. #define GREEN_BITS 6
  31. #define BLUE_BITS  5
  32.  
  33. #define MAX_RED    (1 << RED_BITS)
  34. #define MAX_GREEN  (1 << GREEN_BITS)
  35. #define MAX_BLUE   (1 << BLUE_BITS)
  36.  
  37. #define MAXWEIGHT  128
  38. #define STDWEIGHT_DIV  (2 << 8)
  39. #define STDWEIGHT_MUL  (2 << 10)
  40. #define COLORS     256
  41. #define GAIN       4
  42.  
  43. #define BARGRAPH     "__________\b\b\b\b\b\b\b\b\b\b"
  44. #define BARGRAPHLEN  10
  45.  
  46. int color_cube[MAX_RED][MAX_GREEN][MAX_BLUE];
  47.  
  48. unsigned char clut[COLORS][4];
  49. int erropt[COLORS][4];
  50. enum { red, green, blue, count };
  51. int clutx;
  52.  
  53. int weight_convert[MAXWEIGHT];
  54. int total_weight, cum_weight[MAX_GREEN];
  55. int rep_weight, rep_threshold;
  56. int r, g, b, dr, dg, db;
  57. int dither = 0, verbose = 1;
  58.  
  59. pixval maxval;
  60.  
  61. /*
  62. ** 3-D error diffusion dither routine for points in the color cube; used to
  63. ** select the representative colors.
  64. */
  65. diffuse()
  66. {
  67.   int _7_32nds, _3_32nds, _1_16th;
  68.  
  69.   if (clutx < COLORS) {
  70.     if (color_cube[r][g][b] > rep_threshold) {
  71.  
  72.       clut[clutx][red]   = ((2 * r + 1) * (maxval + 1)) / (2 * MAX_RED);
  73.       clut[clutx][green] = ((2 * g + 1) * (maxval + 1)) / (2 * MAX_GREEN);
  74.       clut[clutx][blue]  = ((2 * b + 1) * (maxval + 1)) / (2 * MAX_BLUE);
  75. #if DUMPCOLORS
  76.       if (verbose > 2) {
  77.         /* Dump new color */
  78.         if ((clutx & 3) == 0) {
  79.           fprintf(stderr, "\n  %3d (%2d): ", clutx, rep_threshold);
  80.         }
  81.         fprintf(stderr,
  82.           " (%03d,%03d,%03d)", clut[clutx][red],
  83.           clut[clutx][green], clut[clutx][blue]
  84.         );
  85.       }
  86. #endif
  87.       ++clutx;
  88.       color_cube[r][g][b] -= rep_weight;
  89.     }
  90.     _7_32nds = (7 * color_cube[r][g][b]) / 32;
  91.     _3_32nds = (3 * color_cube[r][g][b]) / 32;
  92.     _1_16th = color_cube[r][g][b] - 3 * (_7_32nds + _3_32nds);
  93.     color_cube[ r  ][ g  ][ b  ]  = 0;
  94.     /* spread error evenly in color space. */
  95.     color_cube[ r  ][ g  ][b+db] += _7_32nds;
  96.     color_cube[ r  ][g+dg][ b  ] += _7_32nds;
  97.     color_cube[r+dr][ g  ][ b  ] += _7_32nds;
  98.     color_cube[ r  ][g+dg][b+db] += _3_32nds;
  99.     color_cube[r+dr][ g  ][b+db] += _3_32nds;
  100.     color_cube[r+dr][g+dg][ b  ] += _3_32nds;
  101.     color_cube[r+dr][g+dg][b+db] += _1_16th;
  102.     /* Conserve the error at edges if possible (which it is, except the last pixel) */
  103.     if (color_cube[r][g][b] != 0) {
  104.       if      (dg != 0)   color_cube[r][g+dg][b] += color_cube[r][g][b];
  105.       else if (dr != 0)   color_cube[r+dr][g][b] += color_cube[r][g][b];
  106.       else if (db != 0)   color_cube[r][g][b+db] += color_cube[r][g][b];
  107.       else fprintf(stderr, "\nlost error term\n");
  108.     }
  109.   }
  110.   color_cube[r][g][b] = -1;
  111. }
  112.  
  113. /*
  114. ** Find representative color nearest to requested color.  Check color cube
  115. ** for a cached color index.  If not cached, compute nearest and cache result.
  116. */
  117. int nearest_color(pP)
  118.   register pixel *pP;
  119. {
  120.   register unsigned char *test;
  121.   register unsigned i;
  122.   unsigned long min_dist_sqd, dist_sqd;
  123.   int nearest;
  124.   int *cache;
  125.   int r, g, b;
  126.  
  127.   r = ((int)(PPM_GETR(*pP)));
  128.   g = ((int)(PPM_GETG(*pP)));
  129.   b = ((int)(PPM_GETB(*pP)));
  130.   if ((i = maxval + 1) == 256) {
  131.     cache = &(color_cube[r>>(8-RED_BITS)][g>>(8-GREEN_BITS)][b>>(8-BLUE_BITS)]);
  132.   }
  133.   else {
  134.     cache = &(color_cube[(r<<RED_BITS)/i][(g<<GREEN_BITS)/i][(b<<BLUE_BITS)/i]);
  135.   }
  136.   if (*cache >= 0) return *cache;
  137.   min_dist_sqd = ~0;
  138.   for (i = 0; i < COLORS; ++i) {
  139.     test = clut[i];
  140.     dist_sqd = 3 * (r - test[red])   * (r - test[red])
  141.              + 4 * (g - test[green]) * (g - test[green])
  142.              + 2 * (b - test[blue])  * (b - test[blue]);
  143.     if (dist_sqd < min_dist_sqd) {
  144.       nearest = i;
  145.       min_dist_sqd = dist_sqd;
  146.     }
  147.   }
  148.   return (*cache = nearest);
  149. }
  150.  
  151.  
  152. /* Errors are carried at FS_SCALE times actual size for accuracy */
  153. #define _7x16ths(x)   ((7 * (x)) / 16)
  154. #define _5x16ths(x)   ((5 * (x)) / 16)
  155. #define _3x16ths(x)   ((3 * (x)) / 16)
  156. #define _1x16th(x)    ((x) / 16)
  157. #define NEXT(line)    (!(line))
  158. #define FS_SCALE      1024
  159.  
  160. typedef int fs_err_array[2][3];
  161.  
  162. void fs_diffuse (fs_err, line, color, err)
  163.   fs_err_array *fs_err;
  164.   int line, color;
  165.   int err;
  166. {
  167.   fs_err[1] [line]       [color] += _7x16ths(err);
  168.   fs_err[-1][NEXT(line)] [color] += _3x16ths(err);
  169.   fs_err[0] [NEXT(line)] [color] += _5x16ths(err);
  170.   fs_err[1] [NEXT(line)] [color]  = _1x16th(err); /* straight assignment */
  171. }
  172.  
  173. main(argc, argv)
  174.   int argc;
  175.   char *argv[];
  176. {
  177.   FILE *ifd;
  178.   pixel **pixels;
  179.   register pixel *pP;
  180.   int rows, cols, row;
  181.   register int col;
  182.   int limitcol;
  183.   int i, j, k;
  184.   char *ccP;
  185.   int *errP;
  186.   unsigned char *clutP;
  187.   int nearest;
  188.   fs_err_array *fs_err_lines, *fs_err;
  189.   int fs_line = 0;
  190.   char *usage = "[-dither] [-verbose] [ppmfile]";
  191.   char *pm_progname;
  192.   int argn;
  193.  
  194.   ppm_init(&argc, argv);
  195.  
  196.   argn = 1;
  197.   /* option parsing */
  198.   while( argn < argc && argv[argn][0] == '-' && argv[argn][1] != '\0' ) {
  199.     if( pm_keymatch(argv[argn], "-dither", 2) )
  200.         dither = 1;
  201.     else
  202.     if( pm_keymatch(argv[argn], "-nodither", 4) )
  203.         dither = 0;
  204.     else
  205.     if( pm_keymatch(argv[argn], "-verbose", 2) )
  206.         verbose = 1;
  207.     if( pm_keymatch(argv[argn], "-noverbose", 4) || pm_keymatch(argv[argn], "-quiet", 2) )
  208.         verbose = 0;
  209.     else
  210.         pm_usage(usage);
  211.     ++argn;
  212.   }
  213.  
  214.   if( argn < argc ) {
  215.     ifd = pm_openr(argv[argn]);
  216.     ++argn;
  217.   }
  218.   else
  219.     ifd = stdin;
  220.  
  221.   if( argn != argc )
  222.     pm_usage(usage);
  223.  
  224.   if ((pm_progname = strrchr(argv[0], '/')) != NULL) ++pm_progname;
  225.   else pm_progname = argv[0];
  226.  
  227.   /*
  228.   ** Step 0: read in the image.
  229.   */
  230.   pixels = ppm_readppm( ifd, &cols, &rows, &maxval );
  231.   pm_close( ifd );
  232.  
  233.   /*
  234.   ** Step 1: catalog the colors into a color cube.
  235.   */
  236.   if (verbose) {
  237.     fprintf( stderr, "%s: building color tables %s", pm_progname, BARGRAPH);
  238.     j = (i = rows / BARGRAPHLEN) / 2;
  239.   }
  240.  
  241.   /* Count all occurances of each color */
  242.   for (row = 0; row < rows; ++row) {
  243.  
  244.     if (verbose) {
  245.       if (row > j) {
  246.         putc('*', stderr);
  247.         j += i;
  248.       }
  249.     }
  250.  
  251.     if (maxval == 255) {
  252.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  253.         ++(color_cube[PPM_GETR(*pP) / (256 / MAX_RED)]
  254.                      [PPM_GETG(*pP) / (256 / MAX_GREEN)]
  255.                      [PPM_GETB(*pP) / (256 / MAX_BLUE)]
  256.         );
  257.       }
  258.     }
  259.     else {
  260.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  261.         r = (PPM_GETR(*pP) * MAX_RED)  / (maxval + 1);
  262.         g = (PPM_GETG(*pP) * MAX_GREEN)/ (maxval + 1);
  263.         b = (PPM_GETB(*pP) * MAX_BLUE) / (maxval + 1);
  264.         ++(color_cube[r][g][b]);
  265.       }
  266.     }
  267.   }
  268.  
  269.   /*
  270.   ** Step 2: Determine weight of each color and the weight of a representative color.
  271.   */
  272.   /* Initialize logarithmic weighing table */
  273.   for (i = 2; i < MAXWEIGHT; ++i) {
  274.     weight_convert[i] = (int) (100.0 * log((double)(i)));
  275.   }
  276.  
  277.   k = rows * cols;
  278.   if ((k /= STDWEIGHT_DIV) == 0) k = 1;
  279.   total_weight = i = 0;
  280.   for (g = 0; g < MAX_GREEN; ++g) {
  281.     for (r = 0; r < MAX_RED; ++r) {
  282.       for (b = 0; b < MAX_BLUE; ++b) {
  283.         register int weight;
  284.         /* Normalize the weights, independent of picture size. */
  285.         weight = color_cube[r][g][b] * STDWEIGHT_MUL;
  286.         weight /= k;
  287.         if (weight) ++i;
  288.         if (weight >= MAXWEIGHT) weight = MAXWEIGHT - 1;
  289.         total_weight += (color_cube[r][g][b] = weight_convert[weight]);
  290.       }
  291.     }
  292.     cum_weight[g] = total_weight;
  293.   }
  294.   rep_weight = total_weight / COLORS;
  295.  
  296.   if (verbose) {
  297.     putc('\n', stderr);
  298.     if (verbose > 1) {
  299.       fprintf(stderr, "  found %d colors with total weight %d\n",
  300.         i, total_weight);
  301.       fprintf(stderr, "  avg weight for colors used  = %7.2f\n",
  302.         (float)total_weight/i);
  303.       fprintf(stderr, "  avg weight for all colors   = %7.2f\n",
  304.         (float)total_weight/(MAX_RED * MAX_GREEN * MAX_BLUE));
  305.       fprintf(stderr, "  avg weight for final colors = %4d\n", rep_weight);
  306.     }
  307.     fprintf( stderr, "%s: selecting new colors...", pm_progname);
  308.   }
  309.  
  310.   /* Magic foo-foo dust here.  What IS the correct way to select threshold? */
  311.   rep_threshold = total_weight * (28 + 110000/i) / 95000;
  312.  
  313.   /*
  314.   ** Step 3: Do a 3-D error diffusion dither on the data in the color cube
  315.   ** to select the representative colors.  Do the dither back and forth in
  316.   ** such a manner that all the error is conserved (none lost at the edges).
  317.   */
  318. #if !DUMPCOLORS
  319.   if (verbose > 2) {
  320.     fprintf(stderr, "\nrep_threshold: %d", rep_threshold);
  321.   }
  322. #endif
  323.   dg = 1;
  324.   for (g = 0; g < MAX_GREEN; ++g) {
  325.     dr = 1;
  326.     for (r = 0; r < MAX_RED; ++r) {
  327.       db = 1;
  328.       for (b = 0; b < MAX_BLUE - 1; ++b) diffuse();
  329.       db = 0;
  330.       diffuse();
  331.       ++b;
  332.       if (++r == MAX_RED - 1) dr = 0;
  333.       db = -1;
  334.       while (--b > 0) diffuse();
  335.       db = 0;
  336.       diffuse();
  337.     }
  338.     /* Modify threshold to keep rep points proportionally distribited */
  339.     if ((j = clutx - (COLORS * cum_weight[g]) / total_weight) != 0) {
  340.       rep_threshold += j * GAIN;
  341. #if !DUMPCOLORS
  342.       if (verbose > 2) {
  343.         fprintf(stderr, " %d", rep_threshold);
  344.       }
  345. #endif
  346.     }
  347.     if (++g == MAX_GREEN - 1) dg = 0;
  348.     dr = -1;
  349.     while (r-- > 0) {
  350.       db = 1;
  351.       for (b = 0; b < MAX_BLUE - 1; ++b) diffuse();
  352.       db = 0;
  353.       diffuse();
  354.       ++b;
  355.       if (--r == 0) dr = 0;
  356.       db = -1;
  357.       while (--b > 0) diffuse();
  358.       db = 0;
  359.       diffuse();
  360.     }
  361.     /* Modify threshold to keep rep points proportionally distribited */
  362.     if ((j = clutx - (COLORS * cum_weight[g]) / total_weight) != 0) {
  363.       rep_threshold += j * GAIN;
  364. #if !DUMPCOLORS
  365.       if (verbose > 2) {
  366.         fprintf(stderr, " %d", rep_threshold);
  367.       }
  368. #endif
  369.     }
  370.   }
  371.  
  372.   /*
  373.   ** Step 4: check the error associted with the use of each color, and
  374.   ** change the value of the color to minimize the error.
  375.   */
  376.   if (verbose) {
  377.     fprintf( stderr, "\n%s: Reducing errors in the color map %s",
  378.       pm_progname, BARGRAPH);
  379.     j = (i = rows / BARGRAPHLEN) / 2;
  380.   }
  381.   for (row = 0; row < rows; ++row) {
  382.  
  383.     if (verbose) {
  384.       if (row > j) {
  385.         putc('*', stderr);
  386.         j += i;
  387.       }
  388.     }
  389.  
  390.     pP = pixels[row];
  391.     for (col = 0; col < cols; ++col) {
  392.       nearest = nearest_color(pP);
  393.       errP = erropt[nearest]; clutP = clut[nearest];
  394.       errP[red]   += PPM_GETR(*pP) - clutP[red];
  395.       errP[green] += PPM_GETG(*pP) - clutP[green];
  396.       errP[blue]  += PPM_GETB(*pP) - clutP[blue];
  397.       ++errP[count];
  398.       ++pP;
  399.     }
  400.   }
  401. #if DUMPERRORS
  402.     if (verbose) {
  403.       fprintf( stderr, "\n  Color    Red Err  Green Err   Blue Err  Count");
  404.     }
  405. #endif
  406.   for (i = 0; i < COLORS; ++i) {
  407.     clutP = clut[i]; errP = erropt[i];
  408.     j = errP[count];
  409.     if (j > 0) {
  410.       j *= 4;
  411. #if DUMPERRORS
  412.       if (verbose) {
  413.         fprintf( stderr, "\n   %4d %10d %10d %10d %6d",
  414.           i, errP[red]/j, errP[green]/j, errP[blue]/j, j);
  415.       }
  416. #endif
  417.       clutP[red]   += (errP[red]   / j) * 4;
  418.       clutP[green] += (errP[green] / j) * 4;
  419.       clutP[blue]  += (errP[blue]  / j) * 4;
  420.     }
  421.   }
  422.   /* Reset the color cache. */
  423.   for (r = 0; r < MAX_RED; ++r)
  424.     for (g = 0; g < MAX_GREEN; ++g)
  425.       for (b = 0; b < MAX_BLUE; ++b)
  426.         color_cube[r][g][b] = -1;
  427.  
  428.  
  429.   /*
  430.   ** Step 5: map the colors in the image to their closest match in the
  431.   ** new colormap, and write 'em out.
  432.   */
  433.   if (verbose) {
  434.     fprintf( stderr, "\n%s: Mapping image to new colors %s",
  435.       pm_progname, BARGRAPH);
  436.     j = (i = rows / BARGRAPHLEN) / 2;
  437.   }
  438.   ppm_writeppminit( stdout, cols, rows, maxval, 0 );
  439.  
  440.   if (dither) {
  441.     fs_err_lines = (fs_err_array *) calloc((cols + 2), sizeof(fs_err_array));
  442.  
  443.     if (fs_err_lines == NULL) {
  444.       fprintf(stderr, "\n%s: can't allocate Floyd-Steinberg error array.\n",
  445.         pm_progname);
  446.       exit(1);
  447.     }
  448.   }
  449.  
  450.   for (row = 0; row < rows; ++row) {
  451.  
  452.     if (verbose) {
  453.       if (row > j) {
  454.         putc('*', stderr);
  455.         j += i;
  456.       }
  457.     }
  458.  
  459.     if (dither) {
  460.       fs_err = fs_err_lines + 1;
  461.       fs_err[0][NEXT(fs_line)][red]   = 0;
  462.       fs_err[0][NEXT(fs_line)][green] = 0;
  463.       fs_err[0][NEXT(fs_line)][blue]  = 0;
  464.     }
  465.  
  466.     pP = pixels[row];
  467.     for (col = 0; col < cols; ++col) {
  468.  
  469.       if (dither) {
  470.         r = FS_SCALE * (int)(PPM_GETR(*pP)) + fs_err[0][fs_line][red];
  471.         if (r > FS_SCALE * (int)maxval) r = FS_SCALE * (int)maxval;
  472.         if (r < 0) r = 0;
  473.         g = FS_SCALE * (int)(PPM_GETG(*pP)) + fs_err[0][fs_line][green];
  474.         if (g > FS_SCALE * (int)maxval) g = FS_SCALE * (int)maxval;
  475.         if (g < 0) g = 0;
  476.         b = FS_SCALE * (int)(PPM_GETB(*pP)) + fs_err[0][fs_line][blue];
  477.         if (b > FS_SCALE * (int)maxval) b = FS_SCALE * (int)maxval;
  478.         if (b < 0) b = 0;
  479.  
  480.         PPM_ASSIGN(
  481.           *pP, (pixval)(r/FS_SCALE), (pixval)(g/FS_SCALE),
  482.           (pixval)(b/FS_SCALE)
  483.         );
  484.       }
  485.       nearest = nearest_color(pP);
  486.       if (nearest < 0 || nearest > COLORS - 1) {
  487.         fprintf(stderr, "  nearest = %d; out of range\n", nearest);
  488.         exit(1);
  489.       }
  490.       clutP = clut[nearest];
  491.  
  492.       if (dither) {
  493.         r -= FS_SCALE * (int)clutP[red];
  494.         g -= FS_SCALE * (int)clutP[green];
  495.         b -= FS_SCALE * (int)clutP[blue];
  496.  
  497.         fs_diffuse(fs_err, fs_line, red,   r);
  498.         fs_diffuse(fs_err, fs_line, green, g);
  499.         fs_diffuse(fs_err, fs_line, blue,  b);
  500.       }
  501.  
  502.       PPM_ASSIGN( *pP, clutP[red], clutP[green], clutP[blue]);
  503.  
  504.       if (dither) ++fs_err;
  505.       ++pP;
  506.     }
  507.  
  508.     ppm_writeppmrow( stdout, pixels[row], cols, maxval, 0 );
  509.  
  510.     fs_line = NEXT(fs_line);
  511.   }
  512.   if (verbose) {
  513.     fprintf( stderr, "\n%s: done.\n", pm_progname);
  514.   }
  515.  
  516.   exit(0);
  517. }
  518.